/**
 * 
 */
package leetCode;

/**
 * @author zhongfang
 *
 */
public class searchforarange {
    public static int[] searchRange(int[] A, int target) {
        int[] result=new int[2];
        int mid=0;
        int left=0,right=A.length-1;
        //find start
        boolean find=false;
        while(left<=right){
            mid=left+((right-left)>>1);
            if(A[mid]>target){
                right=mid-1;
            }else if(A[mid]==target){
                if(mid==0||A[mid-1]<target){
                    find=true;
                    break;//find start
                }else{//A[start-1]==target,move left
                    right=mid-1;
                }
            }else{//A[start]<target,move right
                left=mid+1;
            }
        }
        if(find==false){
            result[0]=-1;
            result[1]=-1;
            return result;
        }
        result[0]=mid;
        
        //find end
        left=0;
        right=A.length-1;
        while(left<=right){
        	mid=left+(right-left)>>1;
            if(A[mid]>target){//move left
                right=mid-1;
            }else if(A[mid]==target){
                if(mid==A.length-1||A[mid+1]>target){
                    break;//find start
                }else{//A[end+1]==target,move right
                    left=mid+1;
                }
            }else{//A[end]<target,move right
                left=mid+1;
            }
        }
        result[1]=mid;
        return result;
    }
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] A={5,7,7,8,8,10};
		int target=8;
		System.out.println(searchRange(A, target));
	}

}
